home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr10 / gsar106.zip / GSARBMG.C < prev    next >
C/C++ Source or Header  |  1993-06-01  |  18KB  |  509 lines
  1. /* gsarbmg.c *************************************** UPDATED: 930325.18:45 TT
  2.  *
  3.  * Subroutines for fast string searching; no regular expressions
  4.  *
  5.  * Adapted from:
  6.  *
  7.  * Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  8.  * original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  9.  * experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  10.  * practical value.  However, to improve for worst case input, integrating
  11.  * the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  12.  * February 1986) deserves consideration.
  13.  *
  14.  * James A. Woods
  15.  * NASA Ames Research Center
  16.  *
  17.  * 29 April 1986 Jeff Mogul Stanford
  18.  * Adapted as a set of subroutines for use by a program. No
  19.  * regular-expression support.
  20.  *
  21.  * 12 Febuary 1992 Tormod Tjaberg
  22.  * Used parts of the original routines to implement extremely fast
  23.  * file search & replace mechanisms on ASCII & non ASCII files taking
  24.  * care not to 'chop' up the search pattern.
  25.  *
  26.  * Note:
  27.  *
  28.  * If a file consists of the following bytes: 'abrabra' a search for
  29.  * 'abra' will yield two matches. However if we are to replace 'abra'
  30.  * with 'foobar' only one occurrence will be changed and the output
  31.  * file will contain 'foobarbra'.
  32.  *
  33.  * Changes:
  34.  * 930131 : Corrected obscure bug in BMG search function. In some cases the 
  35.  *          character after the actual end of the buffer ( very small file )
  36.  *          could result in a 'LARGE' jump outside the buffer. The solution 
  37.  *          is to make sure that *(strend+1) != *strend.
  38.  * 930104 : Corrected bug in BMGSearchReplace function. If the special case
  39.  *          described above was true 'n' ( number of bytes to write from
  40.  *          search buffer ) would become negative, resulting in a huge file.
  41.  * 920514 : Cleaned up some code, made fwrite more 'consistent'
  42.  *          made the search buffer preallocated
  43.  * 920404 : BMG routines use compile time generated table instead of
  44.  *          filling it in at run time
  45.  *
  46.  * Currently compiles under:
  47.  * Turbo C 2.0, Turbo C++ 1.0, Turbo C++ 3.0, Zortech C++ 3.0,
  48.  * Watcom C 386 8.0, Ultrix ANSI C, Microsoft 6.0, GCC
  49.  */
  50.  
  51. #include <stdio.h>
  52. #include <string.h>
  53. #include <stdlib.h>
  54. #include <ctype.h>
  55. #include <sys/types.h>
  56. #include "comp_dep.h"
  57. #include "gsar.h"
  58.  
  59. #define LARGE  BUFSIZ + PAT_BUFSIZ        /* overshoot purposes */
  60.  
  61. /* Variables needed to perform the BMG search. To gain some speed the ASCII
  62.  * table is set up at compile time. Furthermore the buffer is preallocated
  63.  */
  64.  
  65. int            bmg_patlen;                         /* length of pattern */
  66. unsigned char  bmg_pattern[ PAT_BUFSIZ ];          /* actual pattern */
  67. int            bmg_delta0[ 256 ];                  /* ascii only */
  68. unsigned char  bmg_buffer[ BUFSIZ+PAT_BUFSIZ+2 ];  /* search buffer */
  69. unsigned char  bmg_cmap[ 256 ] =                   /* (un)folded characters */
  70. {    0 ,  1,   2 ,  3,   4,   5 ,  6,   7,   8,   9,  10,  11,
  71.     12 , 13,  14 , 15,  16,  17 , 18,  19,  20,  21,  22,  23,
  72.     24 , 25,  26 , 27,  28,  29 , 30,  31,  32,  33,  34,  35,
  73.     36 , 37,  38 , 39,  40,  41 , 42,  43,  44,  45,  46,  47,
  74.     48 , 49,  50 , 51,  52,  53 , 54,  55,  56,  57,  58,  59,
  75.     60 , 61,  62 , 63,  64,  65 , 66,  67,  68,  69,  70,  71,
  76.     72 , 73,  74 , 75,  76,  77 , 78,  79,  80,  81,  82,  83,
  77.     84 , 85,  86 , 87,  88,  89 , 90,  91,  92,  93,  94,  95,
  78.     96 , 97,  98 , 99, 100, 101 ,102, 103, 104, 105, 106, 107,
  79.    108 ,109, 110 ,111, 112, 113 ,114, 115, 116, 117, 118, 119,
  80.    120 ,121, 122 ,123, 124, 125 ,126, 127, 128, 129, 130, 131,
  81.    132 ,133, 134 ,135, 136, 137 ,138, 139, 140, 141, 142, 143,
  82.    144 ,145, 146 ,147, 148, 149 ,150, 151, 152, 153, 154, 155,
  83.    156 ,157, 158 ,159, 160, 161 ,162, 163, 164, 165, 166, 167,
  84.    168 ,169, 170 ,171, 172, 173 ,174, 175, 176, 177, 178, 179,
  85.    180 ,181, 182 ,183, 184, 185 ,186, 187, 188, 189, 190, 191,
  86.    192 ,193, 194 ,195, 196, 197 ,198, 199, 200, 201, 202, 203,
  87.    204 ,205, 206 ,207, 208, 209 ,210, 211, 212, 213, 214, 215,
  88.    216 ,217, 218 ,219, 220, 221 ,222, 223, 224, 225, 226, 227,
  89.    228 ,229, 230 ,231, 232, 233 ,234, 235, 236, 237, 238, 239,
  90.    240 ,241, 242 ,243, 244, 245 ,246, 247, 248, 249, 250, 251,
  91.    252 ,253, 254 ,255
  92. };
  93.  
  94. /* function prototypes internal to this module */
  95. void Verbose( OUTPUT_CTRL *, unsigned long , int ,
  96.               unsigned char *, unsigned char * );
  97.  
  98.  
  99. /* Verbose()
  100.  *
  101.  * Input  : pCtrl - pointer to structure containg output and ctrl info
  102.  *          FileOfs - actual offset in file
  103.  *          BufOfs - match offset in search buffer
  104.  *          pStart - pointer to start of the search buffer
  105.  *          pEnd - pointer to end of the search buffer
  106.  *
  107.  * Returns: nothing
  108.  *
  109.  * Displays buffer information ( filename, offset, context ) according
  110.  * to the flags set in the structure.. i.e. be a bit verbose.
  111.  */
  112. void Verbose( OUTPUT_CTRL *pCtrl, unsigned long FileOfs, int BufOfs,
  113.               unsigned char *pStart, unsigned char *pEnd )
  114. {
  115.    unsigned char *pSC;        /* start of context */
  116.    unsigned char *pEC;        /* end of context */
  117.    unsigned char *pLastSC;    /* last start of context */
  118.  
  119.    unsigned long CtxOfs;      /* context offset */
  120.  
  121.    int i;                     /* loop counter */
  122.  
  123.  
  124.    if ( pCtrl->fFileSpec )                /* display file name */
  125.       fprintf( pCtrl->fpMsg, "%s : ", pCtrl->pInputFile );
  126.  
  127.    if ( pCtrl->fByteOffset )              /* display byte offset */
  128.       fprintf( pCtrl->fpMsg, "0x%lx%s",
  129.                FileOfs + BufOfs,
  130.                ( pCtrl->fTextual ) ? " : " : "" );
  131.  
  132.    /* Display a textual or a hexadecimal context
  133.     */
  134.    if ( pCtrl->fTextual || pCtrl->fHex )
  135.    {
  136.       pSC = pStart + BufOfs - pCtrl->Context/2 + bmg_patlen/2 ;
  137.       if ( pSC < pStart )                /* outside the buffer ? */
  138.          pSC = pStart;
  139.  
  140.       pEC = pSC + pCtrl->Context;
  141.       if ( pEC > pEnd )                  /* outside the buffer ? */
  142.       {
  143.          pEC = pEnd;
  144.  
  145.          /* if we have to truncate to pEnd readjust the start
  146.           * of the context if possible.
  147.           */
  148.          if ( pEC - pCtrl->Context  > pStart )
  149.             pSC = pEC - pCtrl->Context;
  150.       }
  151.  
  152.       /* display a hexadecimal context
  153.        */
  154.       if ( pCtrl->fHex )
  155.       {
  156.          fputc( '\n', pCtrl->fpMsg );
  157.  
  158.          CtxOfs = FileOfs + ( pSC - pStart );
  159.  
  160.          while ( pSC != pEC )
  161.          {
  162.             pLastSC = pSC;                /* remember where we started */
  163.  
  164.             fprintf(pCtrl->fpMsg,"0x%08lx: ", CtxOfs );  /* hex offset */
  165.  
  166.             for ( i = 0 ; i < 16 ; i++ )      /* display 16 hex digits */
  167.             {
  168.                if ( pSC != pEC )
  169.                   fprintf(pCtrl->fpMsg,"%02x ", ( unsigned char )  *pSC++ );
  170.                else
  171.                   fprintf(pCtrl->fpMsg,"   ");
  172.             }
  173.  
  174.             pSC = pLastSC;                             /* start again */
  175.  
  176.             for ( i = 0 ; i < 16 ; i++ )     /* display 16 characters */
  177.             {
  178.                if ( pSC != pEC )
  179.                {
  180. #ifdef MSDOS      /* MSDOS can display all characters except CTRL chars */
  181.                   if ( !iscntrl( (int) *pSC ) )
  182. #else             /* its __UNIX__ */
  183.                   if ( isprint( (int) *pSC ) )
  184. #endif
  185.                      fputc( *pSC, pCtrl->fpMsg );
  186.                   else
  187.                      fputc( '.', pCtrl->fpMsg );
  188.  
  189.                   pSC++;
  190.                }
  191.             }
  192.             CtxOfs += 16;             /* increment context offset by 16 */
  193.             fputc('\n',pCtrl->fpMsg);
  194.          }
  195.  
  196.       }
  197.  
  198.       /* display textual context...
  199.        */
  200.       if ( pCtrl->fTextual )
  201.       {
  202.          while ( pSC != pEC  )
  203.          {
  204. #ifdef MSDOS   /* MSDOS can display all characters except CTRL chars */
  205.             if ( !iscntrl( (int) *pSC ) )
  206. #else          /* its __UNIX__ */
  207.             if ( isprint( (int) *pSC ) )
  208. #endif
  209.                fputc( *pSC, pCtrl->fpMsg );
  210.             else
  211.                fputc( '.', pCtrl->fpMsg );
  212.  
  213.             pSC++;
  214.          }
  215.       }
  216.    }
  217.  
  218.    if ( !pCtrl->fHex )
  219.       fputc('\n',pCtrl->fpMsg);
  220. }
  221.  
  222.  
  223.  
  224. /* BMGSearch()
  225.  *
  226.  * Input    : pCtrl - pointer to structure containg output and ctrl info
  227.  * Returns  : number of matches found in file
  228.  *
  229.  * The pattern to search for must already have been set up using BMGSetup
  230.  *
  231.  * Works by applying BMG algorithm to a buffer. To ensure the pattern is not
  232.  * inadvertently chopped up, patlen -1 bytes is always moved to the
  233.  * start of the buffer. And the start of the buffer moved backwards
  234.  * accordingly. If the last match was within the patlen - 1 bytes at
  235.  * the end, only the remaining bytes are transferred.
  236.  */
  237. long BMGSearch( OUTPUT_CTRL *pCtrl )
  238. {
  239.    register unsigned char *k;
  240.    register unsigned char *s;
  241.    register unsigned char *strend;
  242.  
  243.    register int j;
  244.  
  245.    int  nTrans = 0;   /* number of bytes to transfer to the start of the buffer */
  246.    int  BufOfs;       /* buffer offset for each match */
  247.    int  BufLen;       /* actual length of buffer + nTrans */
  248.  
  249.    long nMatches = 0; /* number of matches found */
  250.  
  251.    unsigned char  *pStart;    /* Start of buffer to search */
  252.    unsigned char  *pEnd;      /* End of buffer to search */
  253.    unsigned char  *pFileBuf;  /* Start of file contents */
  254.  
  255.    unsigned long nBytes;      /* number of bytes read */
  256.    unsigned long FileOfs = 0; /* current file offset */
  257.  
  258.  
  259.    pStart = &bmg_buffer[ bmg_patlen - 1 ]; /* past the pattern at the start */
  260.    pFileBuf = pStart;                      /* where to store the file block */
  261.    for (;;)
  262.    {
  263.       nBytes = (unsigned long) fread( pFileBuf, 1,( size_t ) BUFSIZ, pCtrl->fpIn );
  264.       pEnd = pFileBuf + nBytes;
  265.  
  266.       BufOfs = -1;              /* -1 is returned if no match found */
  267.       s = pStart;
  268.  
  269.       BufLen = nBytes + nTrans;
  270.       strend = pStart + BufLen;
  271.       *(strend+1) = ~(*strend); /* sentinel to prevent jump out of buffer */
  272.       k = pStart + bmg_patlen - 1;
  273.  
  274.       for (;;)
  275.       {
  276.          while ((k += bmg_delta0[ *(unsigned char *) k ]) < strend) ;
  277.          if (k < ( pStart + LARGE))
  278.             break;
  279.          k -= LARGE;
  280.  
  281.          j = bmg_patlen - 1;
  282.          s = k - 1;
  283.  
  284.          while (bmg_cmap[*s--] == bmg_pattern[--j]) ;
  285.          if (j >= 0)
  286.             k++;
  287.          else
  288.          {  /* found submatch, k is on the last letter in the match */
  289.  
  290.             BufOfs =  k - pStart + 1 - bmg_patlen;
  291.             nMatches++;
  292.             if ( pCtrl->fVerbose )
  293.                Verbose( pCtrl , FileOfs, BufOfs, pStart, pEnd );
  294.  
  295.             k++;
  296.             if (k >= strend)
  297.                break;
  298.          }
  299.       }
  300.  
  301.       if ( BufOfs == -1  )       /* no match transfer patlen - 1 bytes to buffer start */
  302.          nTrans = bmg_patlen -1; /* to be sure that we don't skip a pattern */
  303.       else                       /* we have a match, but where ? */
  304.       {
  305.          nTrans = pEnd - ( pStart + BufOfs + bmg_patlen );  /* calculate the remaining buffer */
  306.                                                             /* space after last match */
  307.          if ( nTrans >= bmg_patlen )  /* not between End & End - patlen -1 */
  308.             nTrans = bmg_patlen - 1;  /* Transfer patlen - 1 bytes */
  309.       }
  310.       FileOfs = FileOfs + BufLen - nTrans;  /* calculate file offset  */
  311.  
  312.       if ( nTrans == 0 )              /* match at exact end of buffer */
  313.          pStart = pFileBuf;
  314.       else
  315.       {
  316.          pStart = pFileBuf - nTrans;  /* move start pointer accordingly */
  317.          memcpy( pStart, pEnd - nTrans, nTrans ); /* move remaining bytes to the start */
  318.       }
  319.       if ( feof( pCtrl->fpIn ) )  
  320.          break;
  321.    }
  322.    return nMatches;
  323. }
  324.  
  325.  
  326. /* BMGSearchReplace()
  327.  *
  328.  * Input    : pCtrl - pointer to structure containg output and ctrl info
  329.  *            ReplaceBuf - pointer to buffer which contains replacement
  330.  *            nReplace - number of bytes in replace buffer
  331.  *
  332.  * Returns  : number of matches & replaces performed
  333.  *            -1 if error in fwrite, disk might be full, or removed
  334.  *
  335.  * The pattern to search for must already have been set up using BMGSetup
  336.  *
  337.  * Works by applying BMG algorithm to a buffer. To ensure the pattern is not
  338.  * inadvertently chopped up, patlen -1 bytes is always moved to the
  339.  * start of the buffer. And the pointer to the start of the buffer moved
  340.  * backwards accordingly. If the last match was within the patlen - 1 bytes
  341.  * at the end, only the remaining bytes are transferred.
  342.  */
  343. long BMGSearchReplace( OUTPUT_CTRL *pCtrl,  char * ReplaceBuf, unsigned short nReplace )
  344. {
  345.    register unsigned char *k;
  346.    register unsigned char *strend;
  347.    register unsigned char *s;
  348.  
  349.    register int j;
  350.    register int n;    /* n is number of bytes to write */
  351.  
  352.    int  nTrans = 0;   /* number of bytes to transfer to the start of the buffer */
  353.    int  BufOfs;       /* buffer offset for each match */
  354.    int  BufLen;       /* actual length of buffer + nTrans */
  355.  
  356.    long nMatches = 0; /* number of matches found */
  357.  
  358.    unsigned char *pLast;      /* Where to write the replacement from */
  359.    unsigned char *pStart;     /* Start of buffer to search */
  360.    unsigned char *pEnd;       /* End of buffer to search */
  361.    unsigned char *pFileBuf;   /* Start of file contents, constant throughout 
  362.                                  the entire search */
  363.  
  364.    unsigned long nBytes;      /* number of bytes read */
  365.    unsigned long FileOfs = 0; /* current file offset */
  366.  
  367.  
  368.    pStart = &bmg_buffer[ bmg_patlen - 1 ];  /* past the pattern at the start */
  369.    pFileBuf = pStart;                       /* where to store the file block */
  370.    for (;;)
  371.    {
  372.       nBytes = (unsigned long) fread( pFileBuf, 1,( size_t ) BUFSIZ, pCtrl->fpIn );
  373.       pEnd = pFileBuf + nBytes;
  374.  
  375.       BufOfs = -1;              /* -1 is returned if no match found */
  376.       pLast = s = pStart;
  377.  
  378.       BufLen = nBytes + nTrans;
  379.       strend = pStart + BufLen;
  380.       *(strend+1) = ~(*strend); /* sentinel to prevent jump out of buffer */
  381.       k = pStart + bmg_patlen - 1;
  382.  
  383.       for (;;)
  384.       {
  385.          while ((k += bmg_delta0[ *(unsigned char *) k ]) < strend) ;
  386.          if (k < ( pStart + LARGE))
  387.             break;
  388.          k -= LARGE;
  389.  
  390.          j = bmg_patlen - 1;
  391.          s = k - 1;
  392.  
  393.          while (bmg_cmap[*s--] == bmg_pattern[--j]) ;
  394.          if (j >= 0)
  395.             k++;
  396.          else
  397.          {  /* found submatch, k is on the last letter in the match */
  398.             BufOfs =  k - pStart + 1 - bmg_patlen;
  399.  
  400.             /* number of bytes to write from buffer */
  401.             n =  ( pStart + BufOfs ) - pLast;
  402.  
  403.             if ( n >= 0 )
  404.             {
  405.                nMatches++;
  406.                if ( pCtrl->fVerbose )
  407.                   Verbose( pCtrl , FileOfs, BufOfs, pStart, pEnd );
  408.  
  409.                if ( fwrite( pLast, ( size_t ) 1, n, pCtrl->fpOut ) != n )
  410.                   return -1;
  411.  
  412.                /* write replacement array, return -1 if error */
  413.                if ( fwrite( ReplaceBuf, ( size_t ) 1, nReplace, pCtrl->fpOut ) != nReplace )
  414.                   return -1;
  415.  
  416.                k++;
  417.                pLast = k;      /* set last marker to write from */
  418.             }
  419.             else
  420.                k++;            /* special case..see header */
  421.  
  422.             if (k >= strend)
  423.                break;
  424.          }
  425.       }
  426.  
  427.       if ( BufOfs == -1  )   /* no match transfer patlen - 1 bytes to buffer start */
  428.          nTrans = bmg_patlen -1; /* to be sure that we don't ignore a pattern */
  429.       else                   /* we have a match, but where ? */
  430.       {
  431.          nTrans = pEnd - ( pStart + BufOfs + bmg_patlen );  /* calculate the remaining buffer */
  432.                                                         /* space after last match */
  433.          if ( nTrans >= bmg_patlen )  /* not between End & End - patlen -1 */
  434.             nTrans = bmg_patlen - 1;  /* Transfer patlen - 1 bytes */
  435.       }
  436.       FileOfs = FileOfs + BufLen - nTrans;  /* calculate file offset  */
  437.  
  438.       if ( !feof( pCtrl->fpIn ) )
  439.       {
  440.          /* write the remainder of the buffer, return -1 if error */
  441.          n =  ( pEnd - nTrans ) - pLast;
  442.          if ( fwrite( pLast, ( size_t ) 1, n, pCtrl->fpOut ) != n )
  443.             return -1;
  444.       }
  445.       else
  446.       {
  447.          /* end of file, dump the rest of the buffer, return -1 if error */
  448.          n = pEnd  - pLast;
  449.          if ( fwrite( pLast, ( size_t ) 1, n, pCtrl->fpOut ) != n)
  450.             return -1;
  451.          break;   /* for */
  452.       }
  453.       if ( nTrans == 0 )        /* match at exact end of buffer */
  454.          pStart = pFileBuf;
  455.       else
  456.       {
  457.          pStart = pFileBuf - nTrans;     /* move start pointer accordingly */
  458.          memcpy( pStart, pEnd - nTrans, nTrans );  /* move remaining bytes to the start */
  459.       }
  460.    }
  461.    return nMatches;
  462. }
  463.  
  464.  
  465. /* BMGSetup()
  466.  *
  467.  * Input    : pat - pointer to pattern string
  468.  *            PatLen - actual length of the pattern
  469.  *            fFolded - flag which determines case folding
  470.  * Returns  : nothing
  471.  *
  472.  * Set up & compute Boyer-Moore delta ( jump ) table
  473.  */
  474. void BMGSetup( char *pat, int PatLen, char fFolded)
  475. {
  476.    register int    j;
  477.  
  478.    bmg_patlen = PatLen;
  479.  
  480.    if (fFolded)
  481.    {  /* fold case while saving pattern */
  482.       for (j = 0; j < bmg_patlen; j++)
  483.          bmg_pattern[j] = (isupper((int) pat[j])
  484.                      ? ( unsigned char) tolower((int) pat[j]) : pat[j]);
  485.    }
  486.    else
  487.       memcpy( bmg_pattern, ( unsigned char * )pat, bmg_patlen );
  488.  
  489.    /* initialisation of bmg_cmap is done at compile time */
  490.    for (j = 0; j < 256; j++)
  491.        bmg_delta0[j] = bmg_patlen;
  492.  
  493.    for (j = 0; j < bmg_patlen - 1; j++)
  494.        bmg_delta0[bmg_pattern[j]] = bmg_patlen - j - 1;
  495.  
  496.    bmg_delta0[bmg_pattern[bmg_patlen - 1]] = LARGE;
  497.  
  498.    if (fFolded)
  499.    {
  500.       for (j = 0; j < bmg_patlen - 1; j++)
  501.          if (islower((int) bmg_pattern[j]))
  502.             bmg_delta0[toupper((int) bmg_pattern[j])] = bmg_patlen - j - 1;
  503.       if (islower((int) bmg_pattern[bmg_patlen - 1]))
  504.          bmg_delta0[toupper((int) bmg_pattern[bmg_patlen - 1])] = LARGE;
  505.       for (j = 'A'; j <= 'Z'; j++)
  506.          bmg_cmap[j] = ( unsigned char) tolower((int) j);
  507.    }
  508. }
  509.